package com.ma.dp.a01;

/**
 * @ClassName Solution416
 * @Author: mayongqiang
 * @DATE 2022/4/9 15:35
 * @Description: 分割等和子集
 */
public class Solution416 {
    /*给定一个只包含正整数的数组，判断是否能分割为等和的两子数组
      转换思路,求数组中是否有一组元素可以组成和为 sum/2
      转换为背包问题: N个元素，价值为nums[i] 背包容量为sum/2  是否能装满
      1、状态和选择：
         状态就是背包的容量和可选择的物品，选择就是装进背包/不装进
      2、dp数组的含义
        dp[i][j] 表示 前i个元素 容量为j 是 是否可以装满   --------  dp[n][sum/2] 就是我们的目标
      3、base case
        dp[0][..]  = false   dp[..][0] = true 没有空间相当于装满了
      4、状态转移
        if(j-nums[i-1]<0):
                dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] =  dp[i-1][j] | dp[i-1][j-nums[i-1]]
     */
    public static void main(String[] args) {
        //nums = [1,5,11,5]
        System.out.println(canPartition(new int[]{1, 5, 11, 5}));
    }

    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int n = nums.length;
        if (sum % 2 != 0 || n < 2) {
            return false;
        }
        sum = sum / 2;
        boolean[][] dp = new boolean[n + 1][sum + 1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (j - nums[i - 1] < 0) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }
            }

        }
        /*
            观察到 dp[i][j]都是通过dp[i-1][..]转移过来的,之前的状态必须要保存了
            dp[j]  来替代dp[i-1][j]
             换成一维数组来进行
         */
        boolean[] dp1 = new boolean[sum + 1];
        dp1[0] = true;
        for (int i = 0; i < n; i++) {
            for (int j = sum; j >= 0; j--) {
                if (j - nums[i] >= 0) {
                    dp1[j] = dp1[j] || dp1[j - nums[i]];
                }
            }
        }
        return dp1[sum];
        //return dp[n][sum];
    }

}
